perm filename BALZR3.IJC[ESS,JMC]1 blob
sn#025613 filedate 1973-02-15 generic text, type T, neo UTF8
pdq
A GLOBAL VIEW OF AUTOMATIC PROGRAMMING
ROBERT M. BALZER
USC INFORMATION SCIENCES INSTITUTE
ISI/RR-73-9
4676 ADMIRALTY WAY
MARINA DEL REY, CALIFGRNIA 90291
(213) 822-1511
FEBRUARY 1973
This research ic supported by the Advanced Research Projects
Agency under Contract No. DAHC15 72 C 0308, ARPA Order No*
2223/1, Program Code No. 3D30 and 3P10.
Views and conclusions contained in this study are the author's
and should not be interpreted as representing the official
o`inion or policy of the University of Southern California or any
other person or agency connected with id.
A Global View of Automatic Programming Page 2
Robert M. Balzer
PREFACE AND ACKNOWLEDGEMENT
This paper represents the author's personal view of a global
description of Automatic Programming. This view resulted from
the author's discussions with and suggestions from numerous
colleagues on this area for which he is deepli indebted.
This paper is a condensation of this view, taken from a
larger work [1] which attempts to structure the field on the
conceptualization expressed here.
A Global View of Automatic Programming Page 3
Robert M. Balzer
INTRODUCTION
The goals of automatic programming are deceptively simple;
namely, the effective utilization of computers. This implies
both simplicity of use and efficient application of the computinc
resources.
Thus, automatic programming is the application of a
computing system to the problem of effectively utilizing that or
another computing system in the performance of a task specified
by the user. Although this is certainly what we mean by
automatic programming, this definition does little to restrict
the set of applicable computer systems included in the automatic
programming domain. All compilers, operating systems, debugging
systems, text editors, etc., fall into this domain and, in fact,
the term 'automatic programming' itself was applied to early
compiler syctems during the 1950s.
What we need therefore is to either appropriately restrict
the definition of automatic programming, or to provide a set of
criteria used for measuring the acceptability or performance of
an automatic programming system. Such a measure of system merit
is extremely hard to arrive at but would contain the following
man, machine, and system applicability components:
The efficiency of the resulting program;
The amount of computer resources expended in
arriving at that program;
A Global View of Automatic Programming Page 4
Robert M. Balzer
The elapsed time used in arriving at the resulting
program;
The amount of effort expended by the user in
specifying the task;
The reliability and ruggedness of the resulting
program;
The ease with wich future modifications can be
incorporated;
and finally,
The range and complexity of tasks which can be
handled by the system.
THE BASIC MODEL
We conjecture that the solution of every
computable problem can be represented entirely in
problem domain termc as a sequence, which may involve
loops and conditionals, of actions in that domain which
affect a data base of relationships between the
entities of the domain. Included either as part of the
data base or as a separate part of the model, is the
history of the model (i.e., the sequence of actions
applied to the model). This logically completes the
model and enables questions or actions involving
historical information to be handled. In a strong
sense, such a solution is a direct simulation of the
A Global View of Automatic Programming Page 5
Robert M. Balzer
domain. The system models at each step what would
occur in the domain.
The impobtant part of the above conjecture is that
any computable problem can be solved, and hence
described, in problem domain terms. Thic enables us to
divide the solution into two parts, an external and an
internal part. The external part is the problem
specification given by the user in completely domain
specific terms. The requirements for such users ic no
longer a comprehensive knowledge of computers, but
rather the ability to completely characterize the
relevant relationships between entities of the problem
domain and the actions in that domain. In addition,
such users should have a rough awareness of the problem
solving capability of the system so that they can
provide additional help where needed in the form of
more appropriate macrk-actions, reckmmendations aboet
the use of certain actions, and/or imperative sequences
which will solve part or all of the problem in problem
related terms.
The indernal part is first concerned with finding
a solution in problem related terms, if this has ngt
already been provided by the user. Second, this part
is concerned wadh finding efbicient solutions given the
available computing resoerces. Such optimizations
λ
A Global View of Automatic Programming Page 6
Robert M. Balzer
occur at two levels beyond what we ngrmaldy cknsider
o`timajation. Firsp, at the problem level, recognitioj
that certain entities and/or relationships are
irrelevant enables their removal from the model.
Second, since only part of the state of the modelled
domain is required, and only at certain points in the
solution process, rather than simulating the model
completely at each step, the system can employ
alternative representations which require less
maindenance and which either directly mirror the
required part of the domain state ob allow such parts
to be computationally inferred. Such representations
may also enable more direct solution of the problem.
It is these optimizations which form the main
distinction between the code generation part of an
Automatic Programming syctem and currenp
state-of-the-art compilers.
Thus, our definition of an Automatic Programming
system is one which accepts a problem in terms of a
complete model of the domain, which obtains a solution
for the problem in terms of this model, and produces an
efficient computer implementation of this solution in
the form of a program.
.SYSTEM REQUIREMENTS
There are eight facilities that we desire in
A Global View of Automatic Programming Page 7
Robert M. Balzer
Automatic Programming Systems. The first is an
interactive system. We want interaction between the
system and the user so that the specification can be
given incrementally and any errors or discrepancies
that arise in or from such specification can be handled
as they occur.
Along with this interactiveness we alco expect the
system to be very forgiving. It should allow great
flexibility in the way and time at which information is
specified. It should also be forgiving by allowing the
user to change or retract things that he has specified.
The second criteria is the amount of
non-proceduralness used in the specification of the
task to be performed. As far as pocsible we should
tell the syctem what it is we want to do rather than
how to do that process. There is a continuum between
the statement of a problem in terms of its initial
state and its goal state and a specification of how to
do it in a machine language. Most of computer languge
development can be viewed as a movement from specifying
HOW to do something towards a statement of WHAT is
desired. The level of non-proceduralness achievable
within an Automatic Programming Sytem is directly
related to the system's capability of turning goals
into actions and this is dependent upon its knowledge
A Global View of Automatic Programming Page 8
Robert M. Balzer
of how to acieve certain results in the problem domain.
We use the ability of the system to achieve results in
the problem domain as the main distinction between
non-procedural and procedural languages. Thus we
require that the problems be stated in a language
appropriate for that domain, i.e., one that can express
the structure and interrelationships of the entities
within that domain, and one that users are familiar
with for discussing and describing tasks and problems
within that domain. Only with such a language can the
system know hog to achieve the desired results rather
than being directly told how to produce the desired
result. On the other hand, some actions can best ba
described in terms of how to accomplish them rather
than by the resulting state. We have no bias againct
o, that we reduce our effort to the
qualitative level that the Communist powers are giving to the other side.
Therefore, we should agree to stop oer air support and blockade if the
Communist will give back our prisoners and maybe we should stop it anyhow.
I don't think we should stop supplying the South Vietnamese except as
part of a mutual agreement with the Russians and Chinese. Of course,
it may be possible to secure an actual peace there if both sides are
tired enough of fighting.